I. Field of the Invention
The present invention relates to communications. More particularly, the present invention relates to a novel and improved method and apparatus for decoding trellis coded modulated data.
II. Description of the Related Art
The field of data communications is concerned with raising the data throughput of a transmission system with a limited signal to noise ratio (SNR). The use of error correcting circuitry such as the Viterbi decoder allows system tradeoffs to be made with smaller SNRs or higher data rates to be used with the same bit error rate (BER). The decrease in the SNR needed is generally referred to as coding gain. Coding gain may be determined from simulated bit error performance curves. In a graph of simulated bit error performance curves the BER of uncoded and various code rate data is charted against E.sub.b /N.sub.o, where E.sub.b is the energy per bit and N.sub.o is the one sided spectral density of the Gaussian White Noise. The coding gain at any point along a bit error performance curve for a particular BER level is determined by subtracting the coded E.sub.b /N.sub.o from the uncoded E.sub.b /N.sub.o. In the paper "Viterbi Decoding for Satellite and Space Communication", by J. A. Heller and I. M. Jacobs, IEEE Transactions on Communication Technology, Vol. COM-19, pgs. 835-848, October 1971, extensive results of simulations on various decoder apparatus were reported.
The coding rate and the generating polynomials are used to define the convolutional code while the coding rate and constraint length are used to define the Viterbi decoder. The coding rate (k/n) corresponds to the number of coding symbols produced (n) for a given number of input bits (k). The coding rate of 1/2 has become one of the most popular rates, although other code rates are also generally used. One class of codes with k.noteq.1 are called punctured codes and are produced by discarding or erasing symbols from the rate 1/n code. The constraint length (K) is the length of the shift register used in the convolutional encoding of the data. A constraint length of K=7 is typical in convolutional coding schemes. The convolutional encoder can be thought of as an Finite Impulse Response (FIR) filter with binary coefficients and length K-1. This filter produces a symbol stream with 2.sup.K-1 possible states.
The basic principle of the Viterbi algorithm is to take a convolutional encoded data stream that has been transmitted over a noisy channel and use a finite state machine to efficiently determine the most likely sequence that was transmitted. The Viterbi algorithm is a computationally efficient method of updating the conditional probabilities of the best state and the most probable bit sequence transmitted from the possible 2.sup.K-1 states. In order to compute this probability, all 2.sup.K-1 states for each bit must be computed. The resulting decision from each of these computations is stored as a single bit in a path memory.
A chainback operation, an inverse of the encoding operation, is performed in which the 2.sup.K-1 decision bits are used to select an output bit. After many branches the most probable path will be selected with a high degree of certainty. The path memory depth must be sufficiently long to be governed by the signal-to-noise ratio and not the length of the chainback memory. For a rate 1/2 code, an exemplary path memory depth is about (5.multidot.K), or 35 branches K=7. For a rate 7/8 punctured code the optimal depth increases to 96 branches.
Constraint lengths of K less than 5 are too small to provide any substantial coding gain, while systems with K greater than 7 are typically too complex to implement as a parallel architecture on a single VLSI device. As the constraint length increases, the number of interconnections in a fully parallel computation section increases as a function of (2.sup.K-1.multidot. L), where L is the number of bits of precision in the state metric computations. Therefore, where K is greater than 7, serial computation devices are generally used which employ large external random access memories (RAMs).
In the paper "Channel Coding with Multilevel/Phase Signal" by G. Ungerboeck, IEEE Transactions on Information Theory, Vol. IT-28, pgs. 55-67, January 1982, a trellis coded modulation (TCM) was described. Ungerboeck showed that within a given spectral bandwidth, it is possible to achieve an Asymptotic Coding Gain of up to 6 dB by employing a rate (n-1)/n convolutional code and doubling the signal set. Unfortunately for each modulation technique and for each bit rate, the maximal coding again is achieved by a different convolutional code. Further disclosed were the results of a search for all convolutional codes for several rates and modulation techniques, and the best codes presented.
In the paper "A Pragmatic Approach to Trellis-Coded Modulation" by A. J. Viterbi, J. K. Wolf, E. Zehavi and R. Padovani, IEEE Communications Magazine, pgs. 11-19, July 1989, a pragmatic approach to trellis coded modulation (PTCM) was disclosed. The underlying concept therein is that a somewhat lower coding gain is achievable by a PTCM based on the "industry standard" rate 1/2, K=7 convolutional code. Although a lower coding gain is realized, it is very close to the coding gain of Ungerboeck at BERs of interest.
A form of trellis coding has previously been implemented in systems employing Quadratrue Amplitude Modulation (QAM). Using QAM modulation techniques both amplitude and phase are used to represent the data contained within the signal. QAM systems, typically 8-QAM and 16-QAM, are commonly used in applications such as wireline communications where channel interference is minimized such that signal amplitude is substantially uneffected. In these applications the signal amplitude can reliably be used in the data representation. However in other applications, such as the satellite communication environment, it is preferred to transmit modulated data at a high signal power, and thus amplitude, to overcome channel interference. In the satellite communication channel the varying of signal amplitude, as required in the QAM technique, results in a greater data error rate.
In order to provide reliable data transmission in the satellite communication channel it is preferred that signal power be held at a constant high power level. In order to achieve this objective, data is transmitted in a PSK modulation scheme with the data contained within the phase of the transmitted signal. It is further desired that a reliable error correction encoding scheme be employed so as to minimize channel error upon the data. It is further desired that such a coding scheme not significantly increase the number of symbols representative of the information bits while still providing an error correction capability. Accordingly, trellis coding meets each of these desires for the encoding of data for transmission, particularly in the satellite channel or other environments in which channel noise can significantly affect the transmitted signal.
Trellis coding is an attractive coding technique since it possesses an aspect which other coding techniques lack. The power of trellis coding lies in the fact that even though no apparent coding operation is performed on any other bit than the least significant bit of the input data, the decoder is able to provide error correction on all bits. Generally the use of TCM techniques to achieve efficient use of power-bandwidth resources has been limited to low speed applications in digital signal processor implementations. The use of PTCM techniques enable VLSI implementations of an encoder/decoder capable of operating at high rates. A decoder using PTCM techniques is capable of handling different modulation techniques, such as M-ary phase-shift keying (M-ary PSK) including Binary PSK (BPSK), Quadrature PSK (QPSK), 8-PSK, and 16-PSK.
It is well known that as the order of M increases in M-ary modulation, more information can be communicated by the increased number of phase points available. However as more points are made available, the possibility increases that noise will more easily shift the points as received. Trellis coding can be characterized as the marriage of coding and modulation so as to provide a higher reliability/higher performance coding technique over comparable convolutional codes for the higher order M-ary modulation.
For example, a rate 2/3 convolutional code has a Hamming metric tuned to BPSK and QPSK modulation. A comparable rate 2/3 trellis code is one in which one bit is encoded at rate 1/2 while the other bit remains uncoded. A properly chosen rate 2/3 trellis code, in general, performs better than the best rate 2/3 convolutional code for 8-PSK modulation.
In implementing an Ungerboeck type trellis code, a decoder of the Viterbi algorithm type can experience parallel branches in the decoding of the coded data. For example a rate 2/3 code infers that four branches come out of each state. Since the rate 2/3 trellis code uses a rate 1/2 code and an uncoded bit, there are two pairs of parallel branches from the one state. As suggested by Ungerboeck, careful selection of the particular code can eliminate a parallel branch problem. However the implementation of a decoder for codes as suggested by Ungerboeck is quite complex and requires a significant amount of circuitry. Such a design is therefore not conducive to a VLSI implementation where other circuit considerations such as power and size can limit the amount of circuitry in the design of preference.
Using the pragmatic trellis code, whose performance nearly achieves that of the Ungerboeck codes, the parallel branches are present in a Viterbi algorithm decoding of the coded data. As a result, the selection of the correct parallel path within a Viterbi decoder itself can require complex circuitry. When a VLSI implementation is desired the additional circuitry required again raises circuit limiting issues.
It is therefore an object of the present invention to provide a novel and improved method and apparatus for the decoding of trellis encoded data.
Its is another object of the present invention to provide a trellis decoder of minimum circuitry for pragmatic trellis codes.
It is yet another object of the present invention to provide in a trellis decoder a novel and improved method and circuitry for resolving certain phase ambiguities in the received coded data caused by channel impairments.